convergence to stationary point

Theorem

For any β-smooth differentiable function $f$ (convex or not), if we run GD for $T$ steps, we can find a point $\hat{\mathbf{x}}$ such that:

Corollary

If $T \geq \frac{2\beta}{T}$, then $||\nabla f(\hat{\mathbf{x}})||_2^2 \leq \epsilon \left(f(\mathbf{x}^{(0)})-f(\mathbf{x}^*)\right)$.

see: stationary point, convergence